package com.fw.leetcode.binarysearch;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;

/**
 * 349. Intersection of Two Arrays
 *
 * Given two integer arrays nums1 and nums2, return an array of their intersection.
 * Each element in the result must be unique and you may return the result in any order.
 *
 * Example 1:
 *  Input: nums1 = [1,2,2,1], nums2 = [2,2]
 *  Output: [2]
 *
 * Example 2:
 *  Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 *  Output: [9,4]
 *  Explanation: [4,9] is also accepted.
 *
 * Constraints:
 *  1 <= nums1.length, nums2.length <= 1000
 *  0 <= nums1[i], nums2[i] <= 1000
 */
public class Num_0349 implements LeetCode {

    private interface Solution {
        int[] intersection(int[] nums1, int[] nums2);

        default void assertExpected(int[]nums1, int[] nums2, int[] expected) {
            int[] result = intersection(nums1, nums2);
            Arrays.sort(result);
            Arrays.sort(expected);
            if (!Arrays.equals(result, expected)) {
                intersection(nums1, nums2);
            }
        }
    }

    private static class SortBinarySearchSolution implements Solution {

        @Override
        public int[] intersection(int[] nums1, int[] nums2) { // [效果不好] 排序 + 二分：时O(mlogm + nlogn)+O(mlog n) 空O(logm + logn)+O(1)
            if (nums1.length > nums2.length) {
                return intersection(nums2, nums1);
            }
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int i = 0;
            int[] result = new int[nums1.length];
            int idx = 0;

            // 遍历
            int left, right, mid, lastLeft = 0;
            while (i < nums1.length) {
                // 二分
                left = lastLeft;
                right = nums2.length - 1;
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (nums2[mid] == nums1[i]) {
                        if (idx == 0 || nums1[i] != result[idx - 1]) { // 因严格升序，故可以前一个比较来避免重复
                            result[idx++] = nums1[i];
                        }
                        lastLeft = mid + 1;
                        break;
                    } else if (nums2[mid] > nums1[i]) {
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
                i++;
            }
            int[] newResult = result;
            if (idx < result.length) {
                newResult = new int[idx];
                System.arraycopy(result, 0, newResult, 0, idx);
                return newResult;
            }
            return newResult;
        }
    }

    private static class SortDoublePointerSolution implements Solution {

        @Override
        public int[] intersection(int[] nums1, int[] nums2) { // [优] 排序 + 双指针：时O(mlogm + nlogn)+O(m+n) 空O(logm + logn)
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int i = 0;
            int j = 0;
            int[] result = new int[Math.min(nums1.length, nums2.length)];
            int idx = 0;
            while (i < nums1.length && j < nums2.length) {
                if (nums1[i] == nums2[j]) {
                    if (idx == 0 || nums1[i] != result[idx - 1]) { // 因严格升序，故可以前一个比较来避免重复
                        result[idx++] = nums1[i];
                    }
                    i++;
                    j++;
                } else if (nums1[i] < nums2[j]) {
                    i++;
                } else {
                    j++;
                }
            }
            int[] newResult = result;
            if (idx < result.length) {
                newResult = new int[idx];
                System.arraycopy(result, 0, newResult, 0, idx);
                return newResult;
            }
            return newResult;
        }
    }

    public static void main(String[] args) {
        Solution solution = new SortDoublePointerSolution();
        solution.assertExpected(new int[]{1,2,2,1}, new int[]{2,2}, new int[]{2});
        solution.assertExpected(new int[]{4,9,5}, new int[]{9,4,9,8,4}, new int[]{9,4});
    }
}
